package com.lihepeng.leecode.array;

/**
 * 给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
 *
 *
 * 上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/range-sum-query-2d-immutable
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution304 {
    int sums[][] ;
    public Solution304(int[][] matrix) {
        int m = matrix.length;
        if (m>0){
            int n = matrix[0].length;
            sums = new int[m][n+1];
            for (int i=0;i<m;i++){
               for (int j=0;j<n;j++){
                   sums[i][j+1] = sums[i][j]+matrix[i][j];
               }
            }
        }

    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i=row1;i<=row2;i++){
            sum+=(sums[i][col2+1]-sums[i][col1]);
        }
        return sum;
    }
}
